We study the implications for the minimal supersymmetric standard model (MSSM) of the absence of a direct discovery of a Higgs boson at LEP. First we exhibit 15 physically different ways in which one or more Higgs bosons lighter than the LEP limit could still exist. For each of these cases -- as well as the case that the lightest Higgs eigenstate is at, or slightly above, the current LEP limit -- we provide explicit sample configurations of the Higgs sector as well as the soft supersymmetry breaking Lagrangian parameters necessary to generate these outcomes. We argue that all of the cases seem fine-tuned, with the least fine-tuned outcome being that with Higgs mass near 115 GeV. Seeking to minimize this tuning we investigate ways in which the ``maximal-mixing'' scenario with large top-quark trilinear A-term can be obtained from simple string-inspired supergravity models. We find these obvious approaches lead to heavy gauginos and/or problematic low-energy phenomenology with minimal improvement in fine-tuning.